package 力扣.堆;

//import com.sun.jmx.snmp.SnmpUnknownMsgProcModelException;
import sun.print.DialogOnTop;

import java.util.Comparator;
import java.util.PriorityQueue;

public class 可以到达的最远建筑1642 {
    public static void main(String[] args) {

    }

    /** 将消耗的过程转为收集
        寻找落差最大的，用梯子代替，使用梯子的情况：落差和已经大于砖块数量，
     */
    public static int furthestBuilding(int[] heights, int bricks, int ladders) {
           int maxAns = 0;//上行落差和
           int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 1; i < heights.length; i++) {
            int te = heights[i] - heights[i - 1];
            if (te > 0){
                pq.offer(te);
                maxAns += te;
                if (maxAns > bricks){
                    if (ladders > 0){
                        Integer te2 = pq.poll();
                        ladders--;
                        maxAns -= te2;
                    }else {
                        break;
                    }
                }
            }
            ans++;
        }
        return ans;
    }

    public int furthestBuilding2(int[] heights, int bricks, int ladders) {
        if (heights == null || heights.length == 0){
            return -1;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>((Integer o1 , Integer o2) ->{
            return o2 - o1;//Lambda 表达式代替匿名内部类
        });
        int N = heights.length;
        for (int i = 1; i < N; i++) {
            int te = heights[i] - heights[i - 1];
            if (te > 0){//需要往上面跳
                priorityQueue.add(te);
                if (bricks < te){//说明砖块不够用
                    if (ladders > 0){
                        //寻找目前最高的一层楼
                        Integer poll = priorityQueue.poll();
                        bricks += poll;//砖块增加
                        ladders--;//梯子减少
                    }else {
                        return i - 1;
                    }
                }
                bricks -= te;
            }

        }
        return N - 1;
    }
}
